Ball grid array (BGA) is a type of surface-mount packages used for integrated circuits with a high pin density. Wiring patterns are routed between BGA devices to provide signal connections including buses. One proposed routing algorithm determines bus connection paths by seeking a route of each single net (logical connection) such that all the nets constituting a bus will escape out of the boundaries of the components (e.g., BGA devices). Another routing algorithm bundles two or more nets into a single virtual net that is as wide as the sum of individual wire widths. The proposed algorithm routes this virtual net as a single trace, and then splits it back to the original bundle of nets. See, for example, Japanese Laid-open Patent Publication No. 2002-217302. See also Lijuan Luo et al., “B-Escape: A Simultaneous Escape Routing Algorithm Based on Boundary Routing,” Proceedings of the 10th International Symposium on Physical Design, San Francisco, Calif. USA, 2010, pp. 19-25.
When the pin density of devices is high, there would be a number of possible combinations of pins even in a small area. This means that a virtual net may be composed in various ways. It is, therefore, not easy to determine which pins (or which nets) to combine into one bus for routing.